跳到主要内容

理解Paxos算法

Lamport 提出的 Paxos 算法包括两个部分:

  • Basic Paxos 算法:多节点如何就某个值达成共识
  • Multi Paxos 思想:执行多个 Basic Paxos ,就一系列的值达成共识

Basic Paxos

问题

假设一个集群包含三个节点 A, B, C,提供只读 key-value 存储服务。只读 key-value 的意思是指,当一个 key 被创建时,它的值就确定下来了,且后面不能修改。 客户端 1 和客户端 2 同时试图创建一个 X 键。客户端 1 创建值为 "leehao.me" 的 X ,客户端 2 创建值为 "www.leehao.me" 的 X。在这种情况下,集群如何达成共识,实现各节点上 X 的值一致呢?

Paxos 涉及的概念

在 Paxos 算法中,存在提议者(Proposer),接受者(Acceptor),学习者(Learner)三种角色,它们的关系如下:

  • 提议者(Proposer):提议一个值,用于投票表决,可以将上图客户端 1 和客户端 2 看作提议者。实际上,提议者更多是集群内的节点,这里为了演示的方便,将客户端 1 和 2 看作提议者,不影响 Paxos 算法的实质
  • 接受者(Acceptor):对每个提议的值进行投票,并存储接受的值,例如,上图集群内的节点 A、B、C
  • 学习者(Learner):被告知投票的结果,接受达成共识的值,不参与投票的过程,存储接受数据

需要指出的是,一个节点,既可以是提议者,也可以是接受者。 在 Paxos 算法中,使用提案表示一个提议,提案包括提案编号和提议的值。接下来,我们使用 [n, v] 表示一个提案,其中,n 是提案编号,v 是提案的值。 在 Basic Paxos 中,集群中各个节点为了达成共识,需要进行 2 个阶段的协商,即准备(Prepare)阶段和接受(Accept)阶段。

准备阶段

假设客户端 1 的提案编号是 1,客户端 2 的提案编号为 5,并假设节点 A, B 先收到来自客户端 1 的准备请求,节点 C 先收到来自客户端 2 的准备请求。 客户端作为提议者,向所有的接受者发送包含提案编号的准备请求。注意在准备阶段,请求中不需要指定提议的值,只需要包含提案编号即可。 接下来,节点 A,B 接收到客户端 1 的准备请求(提案编号为 1),节点 C 接收到客户端 2 的准备请求(提案编号为 5)。 集群中各个节点在接收到第一个准备请求的处理:

  • 节点 A, B:由于之前没有通过任何提案,所以节点 A,B 将返回“尚无提案”的准备响应,并承诺以后不再响应提案编号小于等于 1 的准备请求,不会通过编号小于 1 的提案
  • 节点 C:由于之前没有通过任何提案,所以节点 C 将返回“尚无提案”的准备响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案

接下来,当节点 A,B 接收到提案编号为 5 的准备请求,节点 C 接收到提案编号为 1 的准备请求:

  • 节点 A, B:由于提案编号 5 大于之前响应的准备请求的提案编号 1,且节点 A, B 都没有通过任何提案,故均返回“尚无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案
  • 节点 C:由于节点 C 接收到提案编号 1 小于节点 C 之前响应的准备请求的提案编号 5 ,所以丢弃该准备请求,不作响应

接受阶段

Basic Paxos 算法第二阶段为接受阶段。当客户端 1,2 在收到大多数节点的准备响应之后会开始发送接受请求。

  • 客户端 1:客户端 1 接收到大多数的接受者(节点 A, B)的准备响应后,根据响应中的提案编号最大的提案的值,设置接受请求的值。由于节点 A, B 均返回“尚无提案”,即提案值为空,故客户端 1 把自己的提议值 "leehao.me" 作为提案的值,发送接受请求 [1, "leehao.me"]
  • 客户端 2:客户端 2 接收到大多数接受者的准备响应后,根据响应中的提案编号最大的提案的值,设置接受请求的值。由于节点 A, B, C 均返回“尚无提案”,即提案值为空,故客户端 2 把自己的提议值 "www.leehao.me" 作为提案的值,发送接受请求 [5, "www.leehao.me"]

当节点 A, B, C 接收到客户端 1, 2 的接受请求时,对接受请求进行处理:

  • 节点 A, B, C 接收到接受请求 [1, "leehao.me"] ,由于提案编号 1 小于三个节点承诺可以通过的最小提案编号 5,所以提案 [1, "leehao.me"] 被拒绝
  • 节点 A, B, C 接收到接受请求 [5, "www.leehao.me"],由于提案编号 5 不小于三个节点承诺可以通过的最小提案编号 5 ,所以通过提案 [5, "www.leehao.me"],即三个节点达成共识,接受 X 的值为 "www.leehao.me"

如果集群中还有学习者,当接受者通过一个提案,就通知学习者,当学习者发现大多数接受者都通过了某个提案,那么学习者也通过该提案,接受提案的值。

接受者存在已通过提案的情况

上面例子中,准备阶段和接受阶段均不存在接受者已经通过提案的情况。这里继续使用上面的例子,不过假设节点 A, B 已通过提案 [5, "www.leehao.me"],节点 C 未通过任何提案。 增加一个新的提议者客户端 3,客户端 3 的提案为 [9,"leehao"] 。 接下来,客户端 3 执行准备阶段和接受阶段。 客户端 3 向节点 A, B, C 发送提案编号为 9 的准备请求: 节点 A, B 接收到客户端 3 的准备请求,由于节点 A, B 已通过提案 [5, "www.leehao.me"],故在准备响应中,包含此提案信息。 节点 C 接收到客户端 3 的准备请求,由于节点 C 未通过任何提案,故节点 C 将返回“尚无提案”的准备响应。 客户端 3 接收到节点 A, B, C 的准备响应后,向节点 A, B, C 发送接受请求。这里需要特点指出,客户端 3 会根据响应中的提案编号最大的提案的值,设置接受请求的值。由于在准备响应中,已包含提案 [5, "www.leehao.me"],故客户端 3 将接受请求的提案编号设置为 9,提案值设置为 "www.leehao.me" 即接受请求的提案为 [9, "www.leehao.me"] 节点 A, B, C 接收到客户端 3 的接受请求,由于提案编号 9 不小于三个节点承诺可以通过的最小提案编号,故均通过提案 [9, www.leehao.me] 概括来说,Basic Paxos 具有以下特点:

  • Basic Paxos 通过二阶段方式来达成共识,即准备阶段和接受阶段
  • Basic Paxos 除了达成共识功能,还实现了容错,在少于一半节点出现故障时,集群也能工作
  • 提案编号大小代表优先级。对于提案编号,接受者提供三个承诺:
    • 如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者承诺不响应这个准备请求
    • 如果接受请求中的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者承诺不通过这个提案
    • 如果按受者已通过提案,那些接受者承诺会在准备请求的响应中,包含已经通过的最大编号的提案信息

Multi Paxos

Basic Paxos 算法只能对单个值达成共识,对于多个值的情形,Basic Paxos 算法就不管用了。因此,Basic Paxos 算法几乎只是用来理论研究,并不直接应用在实际工作中。 Lamport 提出的 Multi Paxos 是一种思想,并不是算法。 Multi Paxos 算法则是一个统称,是指基于 Multi Paxos 思想,通过多个 Basic Paxos 实例实现一系列值的共识的算法(例如 Raft 算法等)。 如果直接通过多次执行 Basic Paxos 实例方式,来实现一系列值的共识,存在以下问题:

  • 如果集群中多个提议者同时在准备阶段提交提案,可能会出现没有提议者接收到大多数准备响应,导致需要重新提交准备请求。例如,在一个 5 个节点的集群中,有 3 个节点同时作为提议者同时提交提案,那就会出现没有一个提议者获取大多数的准备响应,而需要重新提交
  • 为了达成一个值的共识,需要进行 2 轮 RPC 通讯,分别是准备阶段和接受阶段,性能低下

为了解决以上问题,Multi Paxos 引入了领导者(Leader)和优化了 Basic Paxos 的执行过程。

领导者

上面的问题一存在多个提议者同时提交准备请求的情况,如果引入了领导者,由领导者作为唯一的提议者,就可以解决问题一中的冲突的问题。 Lamport 没有说明如何选举领导者,需要在实现 Multi Paxos 算法的时候自行实现。这里我们略去如何选举领导者的算法,假设已经选举出领导者。

优化 Basic Paxos 执行过程

准备阶段的意义,是发现接受者节点上已通过的提案的值。引入领导者后,只有领导者才可发送提议,因此,领导者的提案就已经是最新的了,不再需要通过准备阶段来发现之前被大多数节点通过的提案,领导者可以独立指定提议的值。 这样一来,准备阶段存在就没有意义了,领导者可以直接跳过准备阶段,直接进行接受阶段,减少了 RPC 通讯次数。

Chubby 的 Multi Paxos 实现

Google 分布式锁 Chubby 实现了 Multi Paxos 算法。Chubby 的 Multi Paxos 算法主要包括:

  • Chubby 引入主节点作为领导者,即主节点作为唯一提议者,不存在多个提议者同时提交提案的情况,也不存在提案冲突的情况。Chubby 通过执行 Basic Paxos 算法进行投票选举产生主节点
  • 在 Chubby 中,由于引入了主节点,因此,也去除了 Basic Paxos 的准备阶段
  • 在 Chubby 中,为实现强一致性,所有的读请求和写请求都由主节点来处理
  1. Chubby 所有的写请求由主节点来处理

当主节点接收到客户端的写请求,作为提议者,将数据发送给所有节点,在大多数服务器接受了这个写请求后,给客户端响应写成功。

  1. Chubby 所有的读请求由主节点来处理

当主节点接收到读请求,主节点只需要查询本地数据,然后返回给客户端。 另外,需要指出的是,Basic Paxos 是经过证明的算法。Multi Paxos 是一种思想但缺乏实现算法所需的编程细节,因此,Multi Paxos 的算法实现,是建立在一个未经证明的基础之上。实现 Multi Paxos 算法,最大的挑战是如何证明它是正确的。